package String.easy;

import java.util.Arrays;

/**
 * 1. 问题描述
 *      给你一个字符串 s ，请你根据下面的算法重新构造字符串：
 *
 *
 * 	从 s 中选出 最小 的字符，将它 接在 结果字符串的后面。
 * 	从 s 剩余字符中选出 最小 的字符，且该字符比上一个添加的字符大，将它 接在 结果字符串后面。
 * 	重复步骤 2 ，直到你没法从 s 中选择字符。
 * 	从 s 中选出 最大 的字符，将它 接在 结果字符串的后面。
 * 	从 s 剩余字符中选出 最大 的字符，且该字符比上一个添加的字符小，将它 接在 结果字符串后面。
 * 	重复步骤 5 ，直到你没法从 s 中选择字符。
 * 	重复步骤 1 到 6 ，直到 s 中所有字符都已经被选过。
 *  在任何一步中，如果最小或者最大字符不止一个 ，你可以选择其中任意一个，并将其添加到结果字符串。
 *  请你返回将 s 中字符重新排序后的 结果字符串 。
 *
 * 2. 算法思路
 *      考虑具体的字符串 s = aaabbbcc 定义双指针i,j,初始化指针为i = 0;j = s.length - 1; 创建temp来存储新的字符串
 *      1. aaabbbccc      temp=""
 *         i       j
 *      2. aaabbbccc      temp="a"
 *          i      j
 *      3. aaabbbccc      temp="a"
 *           i     j
 *      4. aaabbbccc      temp="a"
 *            i    j
 *      5. aaabbbccc      temp="ab"
 *             i   j
 *      6. aaabbbccc      temp="ab"
 *              i  j
 *      7. aaabbbccc      temp="ab"
 *               i j
 *      8. aaabbbccc      temp="abc"
 *                ij
 *      9. aaabbbccc      temp="abc"
 *                 j
 *                 i
 *      至此第一轮移动结束,得到的temp="abc"
 *      新一轮的移动开始，在开始移动之前，我们需要将i指针回溯到第一轮位置的下一位，j指针回溯到第一轮位置的前一位
 *      并且交换i,j的移动次序，这次移动让j指针移动
 *      1. aaabbbccc      temp="abc"
 *          i     j
 *      2. aaabbbccc      temp="abcc"
 *          i    j
 *      3. aaabbbccc      tmep="abccb"
 *          i   j
 *      4. aaabbbccc      temp="abccb"
 *          i  j
 *      5. aaabbbccc      temp="abccb"
 *          i j
 *      6. aaabbbccc      temp="abccba"
 *          ij
 *      7. aaabbbccc      temp="abccba"
 *          i
 *          j
 *      至此第二轮移动结束，得到temp="abccba"
 *      新一轮的移动开始，在开始移动之前，重复第一轮结束之后的操作
 *      1. aaabbbccc      temp="abccba"
 *           i   j
 *      2. aaabbbccc      temp="abccbaa"
 *            i  j
 *      3. aaabbbccc      temp="abccbaab"
 *             i j
 *      4. aaabbbccc      temp="abccbaab"
 *              ij
 *      5. aaabbbccc      temp="abccbaabc"
 *               j
 *               i
 *      结束，重复上述操作
 *      1. aaabbbccc  (有问题，此时还可以继续向字符串中添加新的元素，实际上此时需要退出程序，输出结果)
 *            i j
 *
 *      看了leetcode上别人的代码：本质思想就是桶数组法，将s中出现的转化为一个int类型的数组。记录每个字出现
 *      的次数，关键是如何想到使用计数法?
 *
 *      思路分析：
 *
 * 从构造步骤的描述看：（作者的思路非常清晰，赞一个）
 *
 *      需要不断在字符串后面拼接字符，所以使用StringBuilder res = new StringBuilder();来存放答案
 *      先按从小到大的顺序选取一轮字母，再从大到小选取一轮字母。字母被选过就不可以重用，所以涉及到字母的
 *      计数，选取了该字母，就将该字母的剩余可用次数-1。涉及到多轮选取，所以会有外循环。最终所有字母都需
 *      要用上，所以外循环的循环条件为res.length() != s.length()。（所有字母用完时，res的长度即为原字符串的长度）
 *
 *      对于有限个字母的计数，经典方法：可以用int[]代替HashMap，（本题只会出现小写字母）以字符减去a为键，出现次数为值。
 *      当统计完成每个字母的出现次数后，count[i]就表示字母(char)(i + 'a')的剩余可用次数
 *      先按从小到大的顺序选取一轮字母for(int i = 0; i < 26; i++)，如果count[i] == 0，说明该键对应的字母已经用完
 *      了continue，否则就将该字母(char)(i + 'a')添加到res的末尾，并且将其可用次数减一。再按从大到小顺序选取一轮字
 *      母for(int i = 25; i >= 0; i--)，处理方式一致。外循环结束后，返回res.toString()即可。
 *      时间复杂度，由于只是将原字符串的每个字符重排了一次，内循环的数组访问次数是常数26次，所以时间复杂度为O(n)O(n)O(n)。
 *      空间复杂度为O(n)O(n)O(n)。
 *
 *      作者：ustcyyw
 *      链接：https://leetcode-cn.com/problems/increasing-decreasing-string/solution/1370java-yong-shu-zu-dai-ti-hashmapde-xian-xing-su/
 *      来源：力扣（LeetCode）
 *      著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 *  在上述作者的分析中我们可以得到几点比较有用的技巧：
 *      1.字符的计数技巧
 *          一般情况下，我们可以使用hashmap来记录每个字符出现的此时 key为字符，value为该字符出现的次数
 *          但是如果我们记录的只是大写字母或者小写字母，此时我们完全就可以使用int类型的数据来实现：
 *              int[] count = new int[26]; // 创建一个长度为26的数组
 *              s[i]表示s中第i个字符，则s[i] - 'a'就得到s[i]在二十六个字母中的位置
 *              int[s[i]-'a'] += 1 让数组的该位置加1，扫描一遍s就可以得到s中字符出
 *              先的次数
 *
 *              如果我们想要获取通过count数组获取s中第i个字符是什么，我们只需要使用 i + 'a'即可（就是上述一个逆过程）
 *
 *      2.桶数组技巧
 *          思考一下什么情况下可以使用桶数组?
 *
 *
 *
 *
 *
 *
 */


@SuppressWarnings("all")
public class 上升下降字符串 {

    public static void main(String[] args) {
        System.out.println(sortString("leetcode"));
    }

    public static String sortString(String s) {
        int[] count = new int[26];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a'] += 1;
        }
        StringBuilder res = new StringBuilder();
        while (res.length() != s.length()) {
            // 第一遍从小到大循环遍历
            for (int i = 0; i < 26; i++) {
                if (count[i] != 0) {
                    res.append((char)(i+'a'));
                    count[i]--;
                }
            }

            for (int j = 25; j > 0; j--) {
                if (count[j] != 0) {
                    res.append((char)(j+'a'));
                    count[j]--;
                }
            }
        }
        return res.toString();
    }
    public static String sortString1(String s) {
        int[] count = new int[26];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a'] += 1;
        }
        StringBuilder res = new StringBuilder();
        while (res.length() != s.length()) {
            // 第一遍从小到大循环遍历
            for (int i = 0; i < 26; i++) {
                if (count[i] != 0) {
                    res.append((char)(i+'a'));
                    count[i]--;
                }
            }

            for (int j = 25; j > 0; j--) {
                if (count[j] != 0) {
                    res.append((char)(j+'a'));
                    count[j]--;
                }
            }
        }
        return res.toString();
    }
}
